/**
 * 剑指 Offer 33. 二叉搜索树的后序遍历序列
 * https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
 */

/**
 * @param {number[]} arr
 * @param {number} left
 * @param {number} right
 */
function verifySub(arr, left, right) {
  if (right - left < 2) {
    return true;
  }
  const rootVal = arr[right];
  if (rootVal > arr[right - 1]) {
    for (let i = right - 2; i >= left; i -= 1) {
      if (arr[i] > rootVal) {
        return false;
      }
    }
    return verifySub(arr, left, right - 1);
  }
  let lastSmaller = right - 2;
  for (; lastSmaller >= left; lastSmaller -= 1) {
    if (arr[lastSmaller] < rootVal) {
      break;
    }
  }
  if (lastSmaller < left) {
    return verifySub(arr, left, right - 1);
  }
  for (let i = left; i < lastSmaller; i += 1) {
    if (arr[i] > rootVal) {
      return false;
    }
  }
  return verifySub(arr, left, lastSmaller) && verifySub(arr, lastSmaller + 1, right - 1);
}

/**
 * @param {number[]} postorder
 * @return {boolean}
 */
function verifyPostorder(postorder) {
  if (postorder.length < 3) {
    return true;
  }
  return verifySub(postorder, 0, postorder.length - 1);
}

console.log(verifyPostorder([1, 6, 3, 2, 5]) === false);
console.log(verifyPostorder([1, 3, 2, 6, 5]) === true);
